\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

\begin{itemize}
\item
  有三个长度为 \(n\) 的数列
  \(\left\{ a_{1}, a_{2}, . . . , a_{n} \right\}\)
  \(\left\{ b_{1}, b_{2}, . . . , b_{n} \right\}\)
  \(\left\{ c_{1}, c_{2}, . . . , c_{n} \right\}\)
\item
  需要满足约束：

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \item
    \(a_{1} \times x_{1}+a_{2} \times x_{2}+...+a_{n} \times x_{n} \leq P\)
  \item
    \(b_{1} \times x_{1}+b_{2} \times x_{2}+...+b_{n} \times x_{n} \geq P\)
  \item
    \(∀i, x_{i}∈\left\{ 0,1 \right\}\)
  \end{enumerate}
\item
  要求最小化
  \(w=c_{1} \times x_{1}+c_{2} \times x_{2}+...+c_{n} \times x_{n}\)
\item
  其中 \(a_{i},b_{i},c_{i}\) 满足
  \(a_{i} \leq b_{i} \leq   2\times10^{6}\)
\end{itemize}

注意到题目中的关键信息 \(a_{i} \leq b_{i}\)\\
由此可得对于任意一种方案，
\(\sum\limits_{i=1}^nx_ia_i\le\sum\limits_{i=1}^nx_ib_i\) \\
设 \(f[i][j]\) 表示前 \(i\) 项，满足 \(\sum\limits_{i=1}^nx_ia_i\le j\)
且 \(\sum\limits_{i=1}^nx_ib_i≥j\) 时 \(w\) 的最小值

\begin{itemize}
\item
  对 \(a\)，\([-\infty ,j-a_i]+ai<=j\)
\item
  对 \(b\)，\([j-b_i, \infty] + b_i >=j\)
\end{itemize}

所以转移的区间为
\([-\infty ,j-a_i]\cup[j-b_i, \infty] = [j - b_i,j-a_i]\)\\
所以转移方程为：\(f[i][j]=\min \left(\min _{j-b_{i} \leq k \leq j+a_{i}}\left(f[i-1][k]+w_{i}\right), \min (f[i-1][j])\right)\)\\
可以利用单调队列优化，时间复杂度为 \(O(nP)\)

\begin{lstlisting}
const int N = 1e3 + 10 , M = 1e4 + 10;
int n , p , a[N] , b[N] , c[N] , dp[N][M];
signed main()
{
	int T = 1;
	cin >> T;
	while(T --)
	{
		cin >> n >> p;
		rep(i , 1 , n) cin >> a[i];
		rep(i , 1 , n) cin >> b[i];
		rep(i , 1 , n) cin >> c[i];
		memset(dp , 0x3f , sizeof(dp));
		dp[0][0] = 0;
		rep(i , 1 , n)
		{
			rep(j , 0 , p) dp[i][j] = dp[i - 1][j];
			deque<int>deq;
			rep(j , a[i] , p)
			{
				int x = j - a[i];
				while(deq.size() && dp[i - 1][x] <= dp[i - 1][deq.front()]) deq.pop_front();
				deq.push_back(x);
				while(deq.size() && deq.front() < j - b[i])	deq.pop_front();
				if(!deq.size()) continue ;
				dp[i][j] = min(dp[i - 1][j] , dp[i - 1][deq.front()] + c[i]);
			}
		}
		if(dp[n][p] > 2e9) cout << "IMPOSSIBLE!!!\n";
		else cout << dp[n][p] << '\n';
	}
	return 0;
}
\end{lstlisting}

\end{document}
